# -*- coding:utf-8 -*-
'''
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
求二叉树的深度

解题思路：按照之前广度搜索的方式采用层级遍历解法 cur与nextstack存储当前行数的子树节点直到最后一行
'''
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def TreeDepth(self, pRoot):
        cur = []
        if pRoot:
            cur.append(pRoot)
        count = 0
        while cur:
            nextStack = []
            for x in cur:
                if x.right: nextStack.append(x.right)
                if x.left: nextStack.append(x.left)
            cur = nextStack
            count += 1
        return count
        
        # 递归一行解法
        # if pRoot == None: return 0
        # return max(self.TreeDepth(pRoot.left), self.TreeDepth(pRoot.right)) + 1

s = Solution()
s.TreeDepth([])